#include <cstdlib>
#include "sort.h"

void insertion_sort_array(int nums[], int size)
{
    int * tmp = NULL;
    try
    {
        tmp = new int[size];
    }
    catch(std::bad_alloc)
    {
        return;
    }

    int tmp_size = 0;
    int j = 0;
    int k = 0;
    int i = 0;
    for(i = 0; i < size; ++ i)
    {
        for(j = 0; j < tmp_size; ++ j)
        {
            if(nums[i] < tmp[j])
            {
                // once find the first element larger than nums[i]
                // shift all behind elements 1 step back
                for(k = tmp_size; k != j; -- k)
                {
                    tmp[k] = tmp[k - 1];
                }
                break;
            }
        }
        tmp[j] = nums[i];
        ++ tmp_size;
    }
    for(i = 0; i < size; ++ i)
    {
        nums[i] = tmp[i];
    }
    delete [] tmp;
}

